1. Field of the Invention
The present invention relates to a wireless device and a mesh network including the same and more particularly to a wireless device which constitutes an autonomous wireless network and a mesh network including the same.
2. Description of the Related Art
Today, a terminal for ad-hoc networking which incorporates a plurality of interfaces and operates in a multi-channel mode is available and it is possible to construct a multi-channel ad-hoc network.
It has been reported that a multi-channel ad-hoc network provides a better network throughput than a single-channel one (Non-patent Document 1: A. Raniwala, and T. Chiueh, “Architecture and algorithms for an IEEE 802.11-based multi-channel wireless mesh network,” Proc. INFOCOM, 2005. Non-patent Document 2: L. Loyola, T. Kumagai, K. Nagata, S. Otsuki and S. Aikawa, “Multi-channel wireless LAN mesh architecture with DCF-based inter AP communication and idle channel search packet forwarding,” Proc. GLOBECOM'05, Vol. 6, pp. 3279-3284, 2005).
In such multi-channel ad-hoc networks, for higher network performance it is important to properly evaluate multi-channel links according to the condition of each channel and the degree of inter-link interference and reflect the result of evaluation in the transmission of data.
In a multi-channel environment, the degree of interference varies depending on the condition of each channel. Although interference caused by electronic apparatus like microwave ovens or Bluetooth wireless devices is difficult to avoid by a routing algorithm, the influence of interference which depends on the network topology, such as inter-link interference in a network, can be reduced by a routing metric which includes the influence of interference.
Methods which use such metrics to avoid the influence of interference have been proposed (Non-patent Document 3: R. Draves, J. Padhye, and B. Zill, “Routing in multi-radio, multi-hop wireless mesh networks”, in Proc. ACM MOBICOM, pp. 114-128, 2004. Non-patent Document 4: Y. Yang, J. Wang, and R. Kravets, “Designing routing metrics for mesh networks,” Proc. WiMesh'05, 2005. Non-patent Document 5: A. P. Subramanian, M. M. Buddhikot, and S. Miller, “Interference aware routing in multi-radio wireless mesh networks,” Proc. WiMesh'06, 2006).
The method disclosed in Non-patent Document 3 uses a metric which takes the link throughput into consideration. The prior metric ETX (Expected Transmission Count) has been determined only according to packet loss ratio p as expressed by the equation below:
                    [                  Equation          ⁢                                          ⁢          1                ]                                                            ETX        =                  1                      1            -            p                                              (        1        )            
ETX, as calculated by Equation (1), does not consider the link throughput and has a tendency to evaluate even a low-throughput link highly if the packet loss ratio is low. For this reason, ETT (Expected Transmission Time) which considers the magnitude of the throughput is calculated by the equation below:
                    [                  Equation          ⁢                                          ⁢          2                ]                                                            ETT        =                              S            B                    ×          ETX                                    (        2        )            
In Equation (2), S denotes packet size and B denotes data rate.
ETT determined by Equation (2) is substituted into the following equation to determine WCETT (Weighted Cumulative ETT).
                    [                  Equation          ⁢                                          ⁢          3                ]                                                            WCETT        =                                            (                              1                -                β                            )                        ⁢                                          ∑                                  i                  =                  1                                n                            ⁢                                                          ⁢                              ETT                i                                              +                      β            ×                                          max                                  1                  ≤                  j                  ≤                  k                                            ⁢                              X                j                                                                        (        3        )            
In Equation (3), β is a variable parameter which satisfies 0≦β≦1, X denotes the total ETT for a channel, and i denotes hop number.
Since this method considers intra-flow interference but does not consider inter-flow interference, a high throughput cannot be achieved in an environment where there is much inter-flow interference. Besides, metric WCETT does not satisfy isotonicity. Therefore, this method does not guarantee loop-free routing and optimum routing in a proactive hop-by-hop routing protocol.
“Isotonicity” here means that route selection excludes loop routes. A “hop-by-hop routing protocol” means a routing protocol in which a wireless device acting as a repeater makes reference only to the destination of a packet when it selects a route to forward the packet to the destination.
The method described in Non-patent Document 4 considers inter-flow interference and satisfies isotonicity. Specifically this method calculates the metric MIC in accordance with the following equation:
                    [                  Equation          ⁢                                          ⁢          4                ]                                                                                                                                ⁢                                                      MIC                    ⁡                                          (                      p                      )                                                        =                                                                                    1                                                  N                          ×                                                      min                            ⁡                                                          (                              ETT                              )                                                                                                                          ⁢                                                                        ∑                                                      linkl                            ∈                            p                                                                          ⁢                                                                                                  ⁢                                                  IRU                          l                                                                                      +                                                                  ∑                                                  nodei                          ∈                          p                                                                    ⁢                                                                                          ⁢                                              CRC                        i                                                                                                                                                                                    ⁢                                                      IRU                    i                                    =                                                            ETT                      l                                        ×                                          N                      l                                                                                                                                                              ⁢                                                      CRC                    i                                    =                                      {                                                                                                                                                                                      w                                1                                                            ⁢                                                                                                                          ⁢                              if                              ⁢                                                                                                                          ⁢                                                              CH                                ⁡                                                                  (                                                                      prev                                    ⁡                                                                          (                                      i                                      )                                                                                                        )                                                                                                                      ≠                                                          CH                              ⁡                                                              (                                i                                )                                                                                                                                                                                                                                                                                                                                                                                                                w                                      2                                                                        ⁢                                                                                                                                                  ⁢                                    if                                    ⁢                                                                                                                                                  ⁢                                                                          CH                                      ⁡                                                                              (                                                                                  prev                                          ⁡                                                                                      (                                            i                                            )                                                                                                                          )                                                                                                                                              =                                                                      CH                                    ⁡                                                                          (                                      i                                      )                                                                                                                                                                                                                                                                                            0                                  ≤                                                                      w                                    1                                                                    ≤                                                                      w                                    2                                                                                                                                                                                                                                                                                                              }                            (        4        )            
In Equation (4), N is the total number of terminals in the network and min (ETT) is the minimum ETT in the network which is estimated based on the lowest transmission rate for a wireless card. N1 denotes the number of wireless devices in the set of neighbor wireless devices which interfere with each other on link l and CH (i) denotes a channel assigned to terminal i. prev (i) denotes the number of preceding hops along path p for terminal i.
Although the metric MIC does not satisfy isotonicity due to the second term (CRC), isotonicity can be satisfied by the use of a virtual terminal.
The method described in Non-patent Document 5 estimates the influence of interference in detail using the above WCETT metric.